class Node:
    def __init__(self, data=0, lchild=None, rchild=None):
        self.data = data
        self.lchild = lchild
        self.rchild = rchild


class Tree:
    def __init__(self):
        self.root = None
        self.help_queue = []  # help_queue[0]存放当前要插入节点的父节点

    # 层次建树
    def level_build(self, node: Node):
        self.help_queue.append(node)
        if self.root == None:
            self.root = node
        else:
            if self.help_queue[0].lchild == None:  # 没左孩子
                self.help_queue[0].lchild = node
            elif self.help_queue[0].rchild == None:
                self.help_queue[0].rchild = node
                self.help_queue.pop(0)

    # 层次遍历
    def lever_order(self, node: Node):
        help_queue = []
        help_queue.append(self.root)
        while help_queue:
            pop_node = help_queue.pop(0)
            print(pop_node.data, end=' ')
            if pop_node.lchild:
                help_queue.append(pop_node.lchild)
            if pop_node.rchild:
                help_queue.append(pop_node.rchild)

    # 前序遍历
    def pre_order(self, node: Node):
        if node:
            print(node.data, end=' ')
            self.pre_order(node.lchild)
            self.pre_order(node.rchild)

    # 中序遍历
    def mid_order(self, node: Node):
        if node:
            self.mid_order(node.lchild)
            print(node.data, end=' ')
            self.mid_order(node.rchild)

    # 后序遍历
    def late_order(self, node: Node):
        if node:
            self.late_order(node.lchild)
            self.late_order(node.rchild)
            print(node.data, end=' ')


if __name__ == '__main__':
    tree = Tree()
    for i in range(1, 11):
        tree.level_build(Node(i))

    print('层次遍历:', end=' ')
    tree.lever_order(tree.root)
    print()
    print('前序遍历:', end=' ')
    tree.pre_order(tree.root)
    print()
    print('中序遍历:', end=' ')
    tree.mid_order(tree.root)
    print()
    print('后序遍历:', end=' ')
    tree.late_order(tree.root)
